
import java.util.*;

public class Solution {

    public TreeNode head = null;
    public TreeNode pre = null;

    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }

        Convert(pRootOfTree.left);

        if (pre == null) {
            head = pRootOfTree;
            pre = pRootOfTree;
        } else {
            pre.right = pRootOfTree;
            pRootOfTree.left = pre;
            pre = pRootOfTree;
        }

        Convert(pRootOfTree.right);

        return head;
    }

    public TreeNode Convert1(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        TreeNode head = null;
        TreeNode pre = null;
        TreeNode cur = pRootOfTree;

        Stack<TreeNode> stack = new Stack<>();

        boolean isFirst = true;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            if (isFirst) {
                head = cur;
                pre = head;
                isFirst = false;
            } else {
                pre.right = cur;
                cur.left = pre;
                pre = cur;
            }
            cur = cur.right;
        }


        return head;
    }

    //坏键盘
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);

        while (in.hasNextLine()) {
            String s = in.nextLine();
            String strExample = in.nextLine();//7_This_is_a_test
            String strActual = in.nextLine();//_hs_s_a_es
            func(strExample, strActual);//7TI
        }
    }

    private static void func(String strExample, String strActual) {
        Set<Character> set = new HashSet<>();
        //把实际输出的放入set
        for (Character ch : strActual.toUpperCase().toCharArray()) {
            set.add(ch);
        }

        //遍历原来的
        Set<Character> hasPrint = new HashSet<>();
        ;

        for (Character ch : strExample.toUpperCase().toCharArray()) {
            if (!set.contains(ch) && !hasPrint.contains(ch)) {
                System.out.print(ch);
                hasPrint.add(ch);
            }
        }
    }

    //存在重复元素 II
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                if (Math.abs(map.get(nums[i]) - i) <= k) {
                    return true;
                } else {
                    map.put(nums[i], i);
                }
            }
            map.put(nums[i], i);
        }
        return false;
    }

    //前K个高频单词
    //法1：哈希表+排序
    public static List<String> topKFrequent1(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        List<String> rec = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            rec.add(entry.getKey());
        }
        rec.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return map.get(o1) == map.get(o2) ? o1.compareTo(o2) : map.get(o2) - map.get(o1);
            }
        });
        return rec.subList(0, k);
    }

    //法2：优先队列
    public static List<String> topKFrequent2(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        PriorityQueue<Map.Entry<String, Integer>> minHeap =
                new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
                    @Override
                    public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                        return o1.getValue() == o2.getValue() ? o2.getKey().compareTo(o1.getKey())
                                : o1.getValue() - o2.getValue();
                    }
                });
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            minHeap.offer(entry);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        List<String> ret = new ArrayList<>();
        while (!minHeap.isEmpty()) {
            ret.add(minHeap.poll().getKey());
        }
        Collections.reverse(ret);
        return ret;
    }

    public static void main(String[] args) {
        String[] words = {"i", "love", "leetcode", "i", "love", "coding"};
        topKFrequent1(words, 2);
        System.out.println("==========");
    }
}
